The aim of this paper is to construct new Dedekind type sums. We construct generating functions of Barnes' type multiple Frobenius-Euler numbers and polynomials. By applying Mellin transformation to these functions, we define Barnes' type multiple l-functions, which interpolate Frobenius-Euler numbers at negative integers. By using generalizations of the Frobenius-Euler functions, we define generalized Dedekind type sums and prove corresponding reciprocity law. We also give twisted versions of the Frobenius-Euler polynomials and new Dedekind type sums and corresponding reciprocity law. Furthermore, by using p-adic q-Volkenborn integral and twisted (h,q)-Bernoulli functions, we construct p-adic (h,q)-higher order Dedekind type sums. By using relation between Bernoulli and Frobenius-Euler functions, we also define analogues of Hardy-Berndt type sums. We give some new relations related to to these sums as well.